/*
 *  POJ1276: Cash Machine
 */

/*-------- Includes --------*/
#include <iostream>
#include <cstring>

using namespace std;

/*-------- Types --------*/


/*-------- Global Variables --------*/
int cash;
int N;
int num[11];
int den[11];

int dp[11][100001];

/*-------- Function Prototypes --------*/


/*-------- Main Function --------*/
int main(int argc, char const *argv[])
{
    while (cin >> cash >> N) {
        // get input
        for (int i = 1; i <= N; i++) cin >> num[i] >> den[i];

        // cut off
        if (cash == 0 || N == 0) {
            cout << 0 << endl;
            continue;
        }

        // initialize
        memset(dp, 0, sizeof(dp));

        dp[0][cash] = 1;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= cash; j++) {
                if (dp[i - 1][j]) { // cut off
                    for (int k = 0; k <= num[i]; k++) {
                        if (j >= k * den[i]) dp[i][j - k * den[i]] += dp[i - 1][j];
                    }
                }
            }
        }

        for (int i = 0; i <= cash; i++) {
            if (dp[N][i]) {
                cout << cash - i << endl;
                break;
            }
        }
    }
}

/*-------- Functions --------*/

